import { cbtPrint } from "hy-algokit";
import IHeap from "./IHeap";

class Heap<T> implements IHeap<T> {
  // 定义私有变量_data，用于存储堆中的数据
  private _data: T[] = [];
  // 定义私有变量_size，用于存储堆中数据的数量
  private _size: number = 0;

  // 构造函数，接受一个数组作为参数，如果数组不为空，则调用build_heap方法构建堆
  constructor(arr: T[] = []) {
    if (arr.length > 0) {
      this.build_heap(arr);
    }
  }

  // 定义私有方法swap，用于交换两个元素的位置
  private swap(i: number, j: number): void {
    // 临时变量，用于存储要交换的元素
    const temp = this._data[i];
    // 将要交换的元素赋值给i位置的元素
    this._data[i] = this._data[j];
    // 将i位置的元素赋值给j位置的元素
    this._data[j] = temp;
  }

  // 定义方法insert，用于向堆中插入一个元素
  insert(value: T): void {
    this._data.push(value);
    this._size++;

    let index = this._size - 1;

    // 调用hearfy_up方法，将新插入的元素向上调整
    this.hearfy_up(index);
  }

  // 定义私有方法hearfy_up，用于将新插入的元素向上调整
  private hearfy_up(index: number = this._size - 1): void {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      // 如果新插入的元素小于等于父节点，则不需要调整
      if (this._data[index] <= this._data[parentIndex]) {
        break;
      }
      // 如果新插入的元素大于父节点，则交换位置，并继续向上调整
      if (this._data[index] > this._data[parentIndex]) {
        this.swap(index, parentIndex);
        index = parentIndex;
      }
    }
  }

  // 定义方法extract，用于从堆中提取最小元素
  extract(): T | undefined {
    // 如果堆为空，则返回undefined
    if (this._size === 0) {
      return undefined;
    }
    // 如果堆中只有一个元素，则直接返回该元素
    if (this._size === 1) {
      this._size--;
      return this._data.pop() as T;
    }

    // 将堆顶元素保存下来
    const topValue = this._data[0];
    // 将堆顶元素替换为最后一个元素
    this._data[0] = this._data.pop() as T;
    this._size--;

    // 调用heapify_down方法，将堆顶元素向下调整
    this.heapify_down();

    return topValue;
  }

  // 定义私有方法heapify_down，用于将堆顶元素向下调整
  private heapify_down(index: number = 0): void {
    let start = index;
    // 当堆顶元素有左子节点时，继续向下调整
    while (2 * start + 1 < this._size) {
      const childIndexLeft = start * 2 + 1;
      const childIndexRight = childIndexLeft + 1;
      let largerIndex = childIndexLeft;
      // 如果左子节点小于右子节点，则将largerIndex指向右子节点
      if (
        childIndexLeft < this._size &&
        this._data[childIndexLeft] <= this._data[childIndexRight]
      ) {
        largerIndex = childIndexRight;
      }

      // 如果堆顶元素大于等于较大的子节点，则不需要调整
      if (this._data[start] >= this._data[largerIndex]) {
        break;
      }

      // 否则交换位置，并继续向下调整
      this.swap(index, largerIndex);
      start = largerIndex;
    }
  }

  // 定义方法peek，用于查看堆顶元素
  peek(): T | undefined {
    return this._data[0];
  }

  // 定义方法isEmpty，用于判断堆是否为空
  isEmpty(): boolean {
    return this._size === 0;
  }

  // 定义属性length，用于获取堆中数据的数量
  get length(): number {
    return this._size;
  }

  // 定义方法build_heap，用于构建堆
  build_heap(array: T[]): void {
    this._data = array;
    this._size = array.length;
    const start = Math.floor(this._size / 2 - 1); // 从最后一个非叶子节点开始

    for (let i = start; i >= 0; i--) {
      this.heapify_down(i);
    }
  }

  print(): void {
    // console.log(this._data);
    cbtPrint(this._data);
  }
}

const arr = [56, 23, 45, 11, 9, 20];
const heap = new Heap<number>();
heap.build_heap(arr);
heap.print();

export {};
